1. Field of the Invention
The present invention relates to a system for receiving the digital transmission standards such as DTV (Digital Television) mode and, more particularly to a traceback device off a trellis decoder for ATSC 8VSB (Vestigial Sideband) using the Viterbi decoding algorithm.
2. Discussion of Related Art
The error control and correction technique is generally utilized in the digital communications system to overcome the channel problems such as noise, fading effect and the like. The technique for minimizing errors includes: the channel encoding technique using a convolution encoder in the section of the transmitter, and the channel decoding technique with a Viterbi decoder in the section of the receiver.
FIG. 1 is a block diagram of a general convolution encoder. As shown in FIG. 1, the convolution encoder comprises a 2-bit shift transistor 11 and two adders 12 and 12' for executing modulo-two addition. Outputs G1 and G2 are determined according to the states contained in the shift register 11 and an input 13.
The outputs G1 and G2 are represented over time in the trellis diagram shown in FIG. 2. Referring to FIG. 2, each point indicates the state of the shift register 11. The branch of a solid line shows a transition when the input is `0`, that of a dotted line a transition when the input is `1`. Numerals on the branches represent the outputs G1 and G2 when the transition takes place at the respective branches. When two paths combine with each other in the transition, the Viterbi decoder in the section of the receiver chooses a likely path between the two paths but truncates the other by means of the Viterbi decoding algorithm called `maximum likelihood decoding`. The path selected is called a survivor path, containing information as much as a decision depth or truncation depth determined in each state. For example, the bold solid line in FIG. 2 is the survivor path in the state 1 (01) at the time unit 10.
Accordingly, the Viterbi algorithm decodes by choosing the most likely path between the two survivor paths in the respective states to carry out a traceback.
A trellis decoder based on the Viterbi algorithm, as shown in FIG. 3, comprises an input 21, a branch metric arithmetical unit 22 for carrying out all arithmetic and logic operations of the branch metric of the reference value at each branch in the trellis diagram, an ACS (Add-Compare-Select) arithmetical unit 23 for choosing one survivor path in each state and performing arithmetic and logic operations of the state metric of the survivor path, a normalization arithmetical unit 24 for subtracting a maximum likelihood value from the output of the ACS arithmetical unit 23, a state metric memory 25 for storing the state metric, a maximum likelihood value detection unit 26 for detecting one path having the most likely one out of the survivor paths in each state, a path memory 27 for storing information concerning the survivor paths in each state, and a traceback unit 28 for performing a traceback of the survivor path with the output of the maximum likelihood value detection unit 26.
The traceback unit 28, as shown in FIG. 4, comprises a path memory 31 for storing a survivor path as much as a decision depth, a multiplexer 32, a register 33, and a path memory controller 34. The size of the register 33 is equal to K(constraint)-1 and the size of the path memory 31 is M(=2.sup.K-1) * (decision depth). An M-to-1 multiplexer is used for the multiplexer 32.
In the trellis decoder, the traceback unit as constructed above performs a traceback by using the survivor path information at each time unit.
For example, when s.sub.mj is the survivor path information in the state m.sub.j =a.sub.j b.sub.j at the time unit j, the previous state m.sub.j-1 =a.sub.j-1 b.sub.j-1 at a time unit j-1, is given by m.sub.j-1 =b.sub.j s.sub.mj on the survivor path. As understood from the construction of the convolution encoder, b.sub.j =a.sub.j-1, s.sub.mj =b.sub.j-1. In a decoding process, the traceback unit detects a state having the minimum value at each time unit and determines the previous state from the survivor path information stored in the path memory. Such traceback process is repeated as a decision depth (hereinafter, referred to as `L`) and controlled by the path memory controller 34.
While the traceback unit can reduce the cost for hardware by using a single port RAM of M*L, it is adaptable only for the applications of a relatively low clock speed. Thus, the conventional traceback unit must be equipped with an additional control circuit as well as a memory of larger capacity in order to accomplish the traceback in one cycle of the clock.
Another example to overcome the problem as mentioned above is a pipe line type traceback unit as shown in FIG. 5, using the arithmetical device as much as the decision depth. It improves the operational speed of the Viterbi decoder but requires a relatively excessive cost for hardware.
FIG. 6 is a timing diagram of the symbol clock, input and symbol inputs of each trellis decoders to traceback through the conventional traceback unit. Referring to FlG. 6, the maximum decision depth L is limited to 11 because each of the trellis decoders has eleven symbol clocks between the symbol inputs.
The capacity of error control and correction of the trellis decoder depends on the decision depth L. It is thus required that the decision depth must be at least 16 to maintain the segment error rate below 3.times.10.sup.-6 at SNR 14.9 db of GA 8VSB mode. When the decision depth is determined over 12 so as to carry out a traceback in the units of symbol clocks and improve the capacity of error control and correction, the next symbol input is transferred into the trellis decoder to perform another traceback before the previous traceback is completed. Thus a separate control circuit is required in addition to the need of a memory of larger capacity.
Since the transmitter of ATSC 8SVSB mode is in charge of 12 symbol intra-segment interleaving, twelve trellis decoders of the same kind are required in the section of the receiver. The twelve trellis decoders can share the branch metric arithmetical unit, ACS arithmetical unit, maximum likelihood value detector and normalization arithmetical unit by using time-division technique because only one symbol is available every twelve symbols that are transferred to the receiver of the twelve trellis decoders.
Each trellis decoder must have all the state metric memory, path memory and traceback unit, which leads to a considerable increase in the size of the hardware of overall trellis decoder. Since the state metric memory comprises memories as many as the number of states, the cost or hardware is not reduced but it may be taken into consideration to curtail the cost of hardware required in the traceback unit including the expensive path memory.